# -*- coding: utf-8 -*-

'''
projecto- classe destinada ao algoritmo de ordenação: heapsort
autor- Ana Isabel Marques 6052
data de criação do módulo- 29/05/2013

Complexidade Computacional:
        pior caso - O(n log(n))
        caso médio - O(n log(n))
        melhor caso - O(n log(n)) 
'''

import math

class Heapsort:

	'''
	Constructor
	@param A - lista de números inteiros
	'''
	def __init__(self, A):
		self.A = A
		pass

        '''
        Este método permite manter a propriedade de max-heap (valor associado ao nó é
        igual ao do seu nó progenitor. 
        @param i - índice i da tabela
        @param heapsize - tamanho da lista A
        '''
	def max_heapify(self, i, heapsize):

		l = i * 2
		r = i * 2 + 1

		if l <= heapsize and  self.A[l] > self.A[i]:
			largest = l
			pass
		else:
			largest = i
			pass

		if (r <= heapsize) and (self.A[r] > self.A[largest]):
			largest = r
			pass

		if (largest != i):
			self.A[i], self.A[largest] = self.A[largest], self.A[i]
			self.max_heapify(largest, heapsize)
			pass

		pass 

        '''
        Este método constrói um heap a partir de uma sequência de dados
        A[1 ... (len(A)]
        '''
	def build_max_heap(self):
		
		global heapsize
		heapsize = len(self.A) - 1
		
		for i in xrange(int(math.floor(len(self.A)/2)), -1, -1):
			self.max_heapify(i, heapsize)
			pass
		
		pass	

	'''
	Ordena uma lista através do algoritmo de ordenação: heapsort
	Retorna uma lista ordenada
	'''
	def heapsort(self):

		global heapsize

		self.build_max_heap()

		for i in xrange(len(self.A) - 1,0, -1):

			self.A[0], self.A[i] = self.A[i], self.A[0]
			heapsize = heapsize - 1
			self.max_heapify(0, heapsize)
			pass
		
		return self.A
	pass
pass
		



